\documentclass[submission]{FPSAC2017}

\articlenumber{52}
\addbibresource{52_Kim_Lin.bib}


\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}

\usepackage{lipsum}
\usepackage{rotating}
\usepackage{tikz}
%%%%%%%%%%%%%%%%
\def\blue{\textcolor{blue}}
\def\red{\textcolor{red}}
\def\green{\textcolor{green}}
\def\violet{\textcolor{violet}}
\def\cyan{\textcolor{cyan}}

\theoremstyle{plain}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{St}[theorem]{Statement}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{Fact}[theorem]{Fact}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{?}[theorem]{Problem}

\theoremstyle{definition}
\newtheorem{Def}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}

\newtheorem{remark}[theorem]{Remark}


\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\def\lec{\mathrm{lec}}
\def\inv{\mathrm{inv}}
\def\aid{\mathrm{aid}}
\def\ai{\mathrm{ai}}
\def\dc{\mathrm{sw}}
\def\rev{\mathrm{rev}}
\def\comp{\mathrm{comp}}
\def\G{\mathfrak{G}}
\def\DES{\mathrm{DES}}
\def\st{\mathrm{st}}
\def\id{\mathrm{id}}
\def\Fix{\mathrm{FIX}}
\def\fix{\mathrm{fix}}
\def\pix{\mathrm{pix}}
\def\rix{\mathrm{rix}}
\def\aix{\mathrm{aix}}
\def\max{\mathrm{max}}
\def\min{\mathrm{min}}
\def\cont{\mathrm{cont}}
\def\exc{\mathrm{exc}}
\def\dd{\mathrm{dd}}
\def\des{\mathrm{des}}
\def\Des{\mathrm{DES}}
\def\maj{\mathrm{maj}}
\def\imaj{\mathrm{imaj}}
\def\Cont{\mathrm{Cont}}
\def\wex{\mathrm{wex}}
\def\fmaj{\mathrm{fmaj}}
\def\S{\mathfrak{S}}
\def\D{\mathfrak{D}}
\def\T{\mathfrak{T}}
\def\C{\mathfrak{C}}
\def\E{\mathcal{E}}
\def\R{\mathbb{R}}
\def\DE{\mathcal{E}}
\def\W{\mathcal{W}}
\def\G{\mathfrak{G}}
\def\dec{\mathrm{dec}}
\def\tot{\mathrm{tot}}
\def\single{\mathrm{single}}
\def\wlec{\mathrm{wlec}}
\def\rinv{\mathrm{rinv}}
\def\wpix{\mathrm{wpix}}
\def\da{\mathrm{da}}
\def\tg{\mathrm{tg}}
\def\SCF{\mathrm{SCF}}
\def\LG{{L-hook}}
\def\FG{{F-hook}}
\def\cyc{\mathrm{cyc}}
\def\lyc{\mathrm{lyc}}
\def\valley{\mathrm{valley}}
\def\peak{\mathrm{peak}}
\def\cda{\mathrm{cda}}
\def\cdd{\mathrm{cdd}}
\def\Rix{\mathrm{RIX}}
\def\Orb{\mathrm{Orb}}
\def\ST{\mathrm{ST}}
\def\VID{\mathrm{VID}}
\def\LMA{\mathrm{LMA}}
\def\LMI{\mathrm{LMI}}
\def\RMA{\mathrm{RMA}}
\def\RMI{\mathrm{RMI}}
\def\BJP{\mathrm{BJP}}
\def\AVA{\mathrm{AVA}}
\def\lma{\mathrm{lma}}
\def\rma{\mathrm{rma}}

\def\IDES{\mathrm{IDES}}

\def\EUL{\mathrm{EUL}}
\def\eul{\mathrm{eul}}
\def\last{\mathrm{last}}
\def\iasc{\mathrm{iasc}}
\def\m{{\bf m}}

\def\DIST{\mathrm{DIST}}
\def\ZERO{\mathrm{ZERO}}
\def\EMA{\mathrm{EMA}}
\def\Invcode{\mathrm{Invcode}}
\def\Majcode{\mathrm{Majcode}}

\def\zero{\mathrm{zero}}
\def\ema{\mathrm{ema}}

\def\turn{\mathrm{turn}}
\def\Red{\mathrm{red}}
\def\return{\mathrm{return}}
\def\segm{\mathrm{segment}}

\def\lma{\mathrm{lma}}
\def\lmi{\mathrm{lmi}}

\def\neg{\mathrm{neg}}
\def\fexc{\mathrm{fexc}}
\def\imaj{\mathrm{imaj}}
\def\asc{\mathrm{asc}}
\def\ASC{\mathrm{ASC}}

\def\NDD{\mathrm{NDD}}
\def\lrm{\mathrm{lrm}}
\def\Dyck{\mathrm{Dyck}}
\def\area{\mathrm{area}}
\def\rank{\mathrm{rank}}
\def\lrm{\operatorname{lrm}}
\def\NDW{\operatorname{NDW}}
\def\dist{\operatorname{dist}}
\def\EXPO{\operatorname{EXPO}}
\def\CRI{\operatorname{CRI}}
\def\cri{\operatorname{cri}}
\def\lmi{\operatorname{lmi}}

\def\ides{\operatorname{ides}}

\def\max{\operatorname{max}}

\def\ROW{\operatorname{ROW}}

\def\M{\mathcal{M}}
\def\RR{\mathcal{R}}
\def\O{\mathcal{O}}
\def\P{\mathbb{P}}
\def\pos{\operatorname{{\bf pos}}}
\def\area{\operatorname{{area}}}
\def\I{\operatorname{{\bf I}}}
\def\up{\operatorname{{up}}}
\def\val{\operatorname{{val}}}
\def\s{\operatorname{{\bf s}}}
\def\st{\operatorname{st}}
\def\mod{\operatorname{mod}}

\title[Restricted inversion sequences]{Refined restricted inversion sequences}

\author[D. Kim and Z. Lin]{Dongsu Kim\thanks{\href{mailto:dongsu.kim@kaist.ac.kr}{dongsu.kim@kaist.ac.kr}}\addressmark{1} \and Zhicong Lin\thanks{\href{mailto:lin@nims.re.kr}{lin@nims.re.kr}. Supported in part by the National Science Foundation of China grant 11501244.}\addressmark{2}}

\address{\addressmark{1}Department of Mathematical Sciences, Korea Advanced Institute of Science and Technology, Daejeon 305-701, Republic of Korea\\ \addressmark{2}School of Science, Jimei University, Xiamen 361021,
P.R. China
\& CAMP, National Institute for Mathematical Sciences, Daejeon 305-811, Republic of Korea}


\received{\today}

\abstract{Recently, the study of patterns in inversion sequences was initiated by Corteel-Martinez-Savage-Weselcouch and Mansour-Shattuck independently.  Motivated by their  works and a double Eulerian equidistribution due to Foata (1977), we investigate several classical statistics on  restricted inversion sequences that are either known or conjectured to be enumerated by  {\em Catalan}, {\em Large Schr\"oder}, {\em Euler} and {\em Baxter} numbers. One of the two highlights of our results is an intriguing bijection between $021$-avoiding inversion sequences and $(2413,4213)$-avoiding permutations, which proves a sextuple equidistribution involving double Eulerian statistics. The other one is a refinement of a conjecture due to  Martinez and Savage  that the cardinality of $\I_n(\geq,\geq,>)$ is the $n$-th Baxter number, which is proved via the so-called {\em obstinate kernel method} developed by Bousquet-M\'elou.}

\keywords{Inversion sequences, ascents, distinct entries, last entry, Schr\"oder numbers, Baxter numbers}

\begin{document}

\maketitle

\section{Introduction}
For each $n\geq1$, the set of {\em inversion sequences} of length $n$, denoted $\I_n$, is defined by
$\I_n=\{(e_1,e_2,\ldots,e_n): 0\leq e_i<i\}$. It serves as various kind of codings for $\S_n$, the set of
permutations of $[n]:=\{1,2,\ldots,n\}$. By a {\em coding} of $\S_n$, we mean a bijection from $\S_n$ to
$\I_n$. For example, the map $\Theta(\pi): \S_n\rightarrow\I_n$ defined for
$\pi=\pi_1\pi_2\ldots\pi_n\in\S_n$ as
$$
\Theta(\pi)=(e_1,e_2,\ldots,e_n),\quad\text{where $e_i:=|\{j<i: \pi_j>\pi_i\}$}|,
$$
is a natural coding of $\S_n$. Clearly, the sum of the entries of $\Theta(\pi)$ equals the number of
{\em inversions} of $\pi$, i.e., the number of pairs $i<j$ such that $\pi_i>\pi_j$. This is the reason why
$\I_n$ is named inversion sequences here.
  
Pattern avoidance in permutations has already been extensively studied in the literature (see the book
by Kitave~\cite{ki}), while the systematic study of patterns in inversion sequences was initiated only
recently in~\cite{cor} and~\cite{mash}. Since both permutations and inversion sequences will be regarded
as words over $\N=\{0,1,\ldots\}$, their patterns can be defined in a unified way as follows. 

For two words $W=w_1w_2\cdots w_n$ and $P=p_1p_2\cdots p_k$ ($k\leq n$) on $\N$, we say that {\em$W$ contains the pattern $P$} if there  exist  some indices $i_1<i_2<\cdots<i_k$ such that the subword $W'=w_{i_1}w_{i_2}\cdots w_{i_k}$ of $W$  is order isomorphic to $P$. Otherwise, $W$ is said to {\em avoid the pattern $P$}. For example, the word $W=32421$ contains the pattern $231$, because the subword $w_2w_3w_5=241$ of $W$ has the same relative order as $231$. However, $W$ is $101$-avoiding. For a set of words $\mathcal{W}$, the set of words in $\mathcal{W}$ avoiding patterns $P_1,\ldots,P_r$ is denoted by $\mathcal{W}(P_1,\ldots,P_r)$. 
One well-known  enumeration result in this area, attributed to MacMahon and Knuth (cf.~\cite{ki}), is that $|\S_n(123)|=C_n=|\S_n(132)|$, where $C_n:=\frac{1}{n+1}{2n\choose n}$ is the {\em $n$-th Catalan number}.

In~\cite{cor,mash}, inversion sequences avoiding patterns of length $3$ are exploited, where a number of familiar combinatorial sequences, such as {\em large Schr\"oder numbers} (denoted $S_n$) and {\em Euler numbers} (denoted by $E_n$), arise. Martinez and Savage~\cite{ms} further considered a generalization of
pattern avoidance to a fixed triple of binary relations $(\rho_1,\rho_2,\rho_3)$. For each triple of relations
$(\rho_1,\rho_2,\rho_3)\in\{<,\,>,\,\leq,\,\geq,\,=,\,\neq,\,-\}^3$, they studied the set $\I_n(\rho_1,\rho_2,\rho_3)$ consisting of those $e\in\I_n$ with no $i<j<k$ such that $e_i\,\rho_1\,e_j$, $e_j\,\rho_2\,e_k$ and
$e_i\,\rho_3\,e_k$. Here the relation $''-''$ on a set $S$ is all of $S\times S$, i.e.,
$x\,''\!\!-''y$ for all $x,y\in S$. For example, $\I_n(<,>,<)=\I_n(021)$ and $\I_n(\geq,-,\geq)=\I_n(000,101,110)$. In \cref{patt}, we summarize some of their enumeration results and conjectures, as well as corresponding classical facts in permutation patterns.
\begin{figure}
\setlength {\unitlength} {1mm}
\begin {picture} (100,50) \setlength {\unitlength} {1mm}
\thinlines
\put(3,0){\line(1,0){160}}\put(3,50){\line(1,0){160}}\put(13,0){\line(0,1){50}}

\put(5,44){$C_n$}
\put(18,44){$\I_n(132),\I_n(123)$: classical result~\cite{ki}; $\I_n(\geq,-,\geq)$: conjectured in~\cite{ms}}
\put(3,40){\line(1,0){160}}

\put(5,30){$S_n$}
\put(18,32){$\S_n(2413,3142),\S_n(2413,4213),\S_n(3124,3214)$: classical result~\cite{kre}}
\put(18,24){$\I_n(021)$: proved in~\cite{cor,mash}; $\I_n(\geq,\neq,\geq),\I_n(>,-,\geq),\I_n(\geq,-,>)$: proved in~\cite{ms}}
\put(3,20){\line(1,0){160}}

\put(5,14){$B_n$}
\put(18,14){$\S_n(2\underline{41}3,3\underline{14}2)$: classical result~\cite{chung}; $\I_n(\geq,\geq,>)$: conjectured in \cite{ms}}

\put(3,4){\text{$E_{n+1}$}}
\put(18,4){\text{Simsun permutations of $[n]$: classical result \cite{sun}; $I_n(000)$: proved in~\cite{cor}}}
\put(3,10){\line(1,0){160}}
\end{picture}
\caption{Sets enumerated by  $C_n,S_n,B_n$ or $E_{n+1}$.
\label{patt}}
\end {figure}
Based on these results, we will investigate more connections between restricted permutations and inversion sequences by considering several classical statistics that we recall below. 

For each $\pi\in\S_n$ and each $e\in\I_n$, let
$$
\DES(\pi):=\{i\in[n-1]: \pi_i>\pi_{i+1}\}\quad \text{and}\quad\ASC(e):=\{i\in[n-1]: e_i<e_{i+1}\}
$$ 
be the {\em {\bf des}cent set} of $\pi$ and the {\em {\bf asc}ent set} of $e$, respectively. Another important property of the coding $\Theta$ is that $\DES(\pi)=\ASC(\Theta(\pi))$ for each $\pi\in\S_n$. Thus,
\begin{equation}\label{des:asc}
\sum_{\pi\in\S_n}t^{\DES(\pi)}=\sum_{e\in\I_n}t^{\ASC(e)},
\end{equation}
where $t^{S}:=\prod_{i\in S}t_i$ for any set $S$ of positive integers.   
Throughout this paper, we use the convention that if ``$\ST$'' is a set-valued statistic, then ``$\st$'' is the corresponding numerical statistic. For example, $\des(\pi)$ is the cardinality of $\DES(\pi)$ for each $\pi$. It is known that $A_n(t):=\sum_{\pi\in\S_n}t^{\des(\pi)}$ is the classical {\em$n$-th Eulerian polynomial}~\cite{fo} and each statistic whose distribution  gives $A_n(t)$ is called a {\em Eulerian statistic}. In view of~\eqref{des:asc}, ``$\asc$'' is a Eulerian statistic on inversion sequences. Let $\dist(e)$  be the {\em number of {\bf dist}inct positive entries} of $e$. This statistic was first introduced by Dumont~\cite{du}, who also showed that it is a Eulerian statistic on inversion sequences. Amazingly, Foata~\cite{fo} later invented two different codings of permutations  called {\em V-code} and {\em S-code} to prove the following extension of~\eqref{des:asc}.

\begin{theorem}[Foata~1977]\label{foata}
For each $\pi\in\S_n$ let $\ides(\pi):=\des(\pi^{-1})$ be the number of inverse descents of $\pi$. Then,
\begin{equation}\label{dist:asc}
\sum_{\pi\in\S_n}s^{\ides(\pi)}t^{\DES(\pi)}=\sum_{e\in\I_n}s^{\dist(e)}t^{\ASC(e)}.
\end{equation}
\end{theorem}

Partial results regarding the statistics ``$\asc$'' and ``$\dist$'' on restricted inversion sequences
have already been obtained in~\cite{cor,mash,ms}. In particular, the ascent polynomial $S_n(t):=\sum_{e\in\I_n(021)}t^{\asc(e)}$ was shown to be {\em palindromic} via a connection with some {\em black-white rooted binary trees} in~\cite{cor}. Inspired by Foata's result, we will consider the joint distribution of ``$\asc$'' and ``$\dist$'' on restricted inversion sequences and prove several  restricted versions of~\eqref{dist:asc}. 
Another interesting statistic for $e\in\I_n$ is the {\em {\bf last} entry} of $e$, that we denote $\last(e)$. This statistic turns out to be useful in solving some real root problems in~\cite{sv} and will also lead us to solve two enumeration conjectures. 

The rest of this paper deals with refinements of Catalan, Schr\"oder, Baxter and Euler numbers. Two highlights of our results are: (i) a bijection from $\I_n(021)$ to $\S_n(2413,4213)$ (see \cref{sec:sex}); (ii) a refinement of a conjecture due to Martinez and Savage~\cite{ms} that asserts the cardinality of $\I_n(\geq,\geq,>)$ is the $n$-th {\em Baxter number} (denoted $B_n$), which is proved via Bousquet-M\'elou's {\em obstinate kernel method} (see \cref{sec:bax}).

\section{Catalan numbers}
\label{sec:cat}

Let  $(\rho_1,\rho_2,\rho_3)$ be a relation triple in $\{(\geq,-,\geq),(\geq,-,>),(\geq,\geq,>)\}$.
We introduce the parameter $\cri(e)$ for each $e\in\I_n(\rho_1,\rho_2,\rho_3)$, that we call
the {\em {\bf cri}tical value} of $e$, as the minimal integer $c$ such that
$(e_1,\ldots,e_n,c)\in\I_{n+1}(\rho_1,\rho_2,\rho_3)$. Note that ``$\cri$'' depends on the relation triple
$(\rho_1,\rho_2,\rho_3)$.  For example, if we consider $e=(0,1,0,2,2,4)$ as inversion sequence in
$\I_6(\geq,-,>)$, then $\cri(e)=2$. However, $\cri(e)=3$ when $e$ is considered as an inversion sequence
in $\I_6(\geq,-,\geq)$. The reason to introduce ``$\cri$'' is that if $e\in\I_n(\rho_1,\rho_2,\rho_3)$,
then $(e_1,\ldots,e_n,k)$ is in $\I_{n+1}(\rho_1,\rho_2,\rho_3)$ if and only if $\cri(e)\leq k\leq n$.
This parameter will play an important role in our study of the {\em Catalan}, {\em Schr\"oder} and
{\em Baxter triangles} induced by the statistic ``$\last$''. 

As a warm-up, we will first show how the critical value can be used to prove that $|\I_n(\geq,-,\geq)|=C_n$, which was conjectured in~\cite{ms}.
Let us define the refinement
$C_{n,k}:=|\{e\in\I_n(\geq,-,\geq): \last(e)=k\}|$.
The following recurrence shows that the numbers $C_{n,k}$ generate the  {\em Catalan triangle} that has already been widely studied (see~\href{https://oeis.org/A009766}{OEIS: A009766}).
\begin{proposition}\label{cat:tria}
For $0\leq k\leq n-1$, we have the three-term recurrence 
$$
C_{n,k}=C_{n,k-1}+C_{n-1,k}.
$$
\end{proposition}
\begin{proof}
Let $\mathfrak{C}_{n,k}:=\{e\in\I_n(\geq,-,\geq): \last(e)=k\}$. We divide $\mathfrak{C}_{n,k}$ into the disjoint union $\mathfrak{A}_{n,k}\cup\mathfrak{B}_{n,k}$, where $\mathfrak{A}_{n,k}=\{e\in\mathfrak{C}_{n,k}: \cri(e_1,e_2,\ldots,e_{n-1})=k\}$ and $\mathfrak{B}_{n,k}=\mathfrak{C}_{n,k}\setminus\mathfrak{A}_{n,k}$.
Since $\cri(e_1,e_2,\ldots,e_{n-1})\leq k-1$ for $e\in\mathfrak{B}_{n,k}$, the mapping that sends $(e_1,e_2,\ldots,e_{n-1},k)$ to $(e_1,e_2,\ldots,e_{n-1},k-1)$ is a  bijection from $\mathfrak{B}_{n,k}$ to 
$\mathfrak{C}_{n,k-1}$. Therefore, the cardinality of $\mathfrak{B}_{n,k}$ is $C_{n,k-1}$ and so it remains to show that $|\mathfrak{A}_{n,k}|=C_{n-1,k}$. Now, we are going to construct a bijection $g:\mathfrak{A}_{n,k}\rightarrow\mathfrak{C}_{n-1,k}$, which will complete the proof of the recurrence for $C_{n,k}$. For each $e\in\mathfrak{A}_{n,k}$,  there is a unique index $i$ such that $e_i=k-1$ and $e_{i+1}\leq k-1$. Define $g(e)$ to be the inversion sequence obtained from $e$ by deleting $e_{n-1}$, if $e_{n-1}=n-2$, or by deleting $e_i$,
otherwise. For example, we have $g(0,1,1,3,2)=(0,1,1,2)$ while $g(0,1,1,2,2)=(0,1,2,2)$.
It is routine to check that $g$ is actually a bijection.
\end{proof}

\begin{theorem}
For $n\geq1$, we have the equidistribution 
$$
\sum_{\pi\in\S_n(123)}t^{\des(\pi)}=\sum_{e\in\I_n(\geq,-,\geq)}t^{\dist(e)}.
$$
\end{theorem}
\begin{proof}
Let $e\in\I_n(\geq,-,\geq)$. If $t=\max\{i: e_i=i-1\}<n$, then it is straightforward to show that $e$ can be decomposed into two smaller inversion sequences: $(e_1,\ldots,e_{t-1},e_{t+1})$ in $\I_t(\geq,-,\geq)$ 
and $(e_{t+2}-t, e_{t+3}-t,\ldots,e_n-t)$ in $\I_{n-1-t}(\geq,-,\geq)$. Using this decomposition, one can show easily that 
\[
\sum_{n\geq1}x^n\sum_{e\in\I_n(\geq,-,\geq)}t^{\dist(e)}=\frac{-1+2tx(1+x-tx)+\sqrt{1-4tx(1+x-tx)}}{2t^2x(tx-1-x)}.
\]
The desired result then follows by comparing this with the o.g.f.~for $\sum_{\pi\in\S_n(123)}t^{\des(\pi)}$ in~\href{https://oeis.org/A166073}{OEIS: A166073}.
\end{proof}


\section{Schr\"oder numbers}
\subsection{A new Schr\"oder triangle}
\begin{theorem}\label{thm:sch}
For $n\geq1$ and $0\leq k\leq n-1$, we have
\begin{equation}\label{sch:tri}
|\{e\in\I_n(\geq,-,>): \last(e)=k\}|=|\{e\in\I_n(021): \last(e)\equiv k+1 (\mod\,n)\}|.
\end{equation}
\end{theorem}

Note that this result is obviously true for $k=n-1,n-2,n-3$. Let us define the {\em Schr\"oder triangle} 
$S_{n,k}:=|\{e\in\I_n(\geq,-,>): \last(e)=k\}|$.
We have the following simple recurrence for $S_{n,k}$.
\begin{lemma}\label{sch:tri}
For $0\leq k\leq n-3$, we have the  four-term recurrence 
$$
S_{n,k}=S_{n,k-1}+2S_{n-1,k}-S_{n-1,k-1}.
$$
\end{lemma}
\begin{proof}
As in the Catalan case, we divide the set $\mathcal{S}_{n,k}:=\{\I_n(\geq,-,>):\last(e)=k\}$ into
the disjoint union $\mathcal{A}_{n,k}\cup\mathcal{B}_{n,k}$, where 
$\mathcal{A}_{n,k}:=\{e\in\mathcal{S}_{n,k}: \cri(e_1,\ldots,e_{n-1})=k\}$
and $\mathcal{B}_{n,k}=\mathcal{S}_{n,k}\setminus \mathcal{A}_{n,k}$. Clearly, there is a natural bijection
from $\mathcal{B}_{n,k}$ to $\mathcal{S}_{n,k-1}$, which maps $(e_1,\ldots,e_{n-1},k)$ to
$(e_1,\ldots,e_{n-1},k-1)$. Therefore, the cardinality of $\mathcal{B}_{n,k}$ is $S_{n,k-1}$ and so it
remains to show $|\mathcal{A}_{n,k}|=2S_{n-1,k}-S_{n-1,k-1}$, assuming $k\leq n-3$. 
To do this, we further divide $\mathcal{A}_{n,k}$ into the disjoint union
$\mathcal{C}_{n,k}\cup\mathcal{D}_{n,k}$, where 
$$
\mathcal{C}_{n,k}:=\{e\in\mathcal{A}_{n,k}: e_{n-1}=n-2,\ \cri(e_1,\ldots,e_{n-2})=k\}\\
$$
and $\mathcal{D}_{n,k}=\mathcal{A}_{n,k}\setminus\mathcal{C}_{n,k}$. Obviously, we have
$\{(e_1,\ldots,e_{n-2},e_n): e\in \mathcal{C}_{n,k}\}=\mathcal{A}_{n-1,k}$.
Thus,
$|\mathcal{C}_{n,k}|=|\mathcal{A}_{n-1,k}|=|\mathcal{S}_{n-1,k}|-|\mathcal{B}_{n-1,k}|=S_{n-1,k}-S_{n-1,k-1}$,
which will end the proof once we can define a bijection from  $\mathcal{D}_{n,k}$ to $\mathcal{S}_{n-1,k}$. 
 
For each $e\in\mathcal{D}_{n,k}$, if $e_i$ is the left-most entry that equals $\cri(e)=k$,
then the entries $e_i,e_{i+1},\ldots,e_{n-1}$ of $e$ must satisfy: (i) $e_i=k$ and $e_{i+1}\leq k$;
(ii) $k\leq e_{i+2}\leq e_{i+3}\leq\cdots\leq e_{n-1}$, where the inequalities  after the entries greater
than $k$ are strict.
Now removing the right-most entry $e_j$, such that $e_j=k$ and $i\leq j\leq n-1$, from $e$ results in an inversion sequence in $\mathcal{S}_{n-1,k}$ (since $e_{n-1}\leq n-3$) that we denote $f(e)$. For example, we have $f(0,1,2,0,2,2)=(0,1,2,0,2)$, $f(0,1,0,2,2,2)=(0,1,0,2,2)$ and $f(0,1,2,1,3,2)=(0,1,1,3,2)$. We claim that the map $f:\mathcal{D}_{n,k}\rightarrow\mathcal{S}_{n-1,k}$  is a bijection. 
\end{proof}

\begin{proof}[Proof of \cref{thm:sch}]
It is not hard to show that the right-hand side of~\eqref{sch:tri} satisfies the same recurrence relation as $S_{n,k}$, which completes the proof of the theorem.
\end{proof}

One may ask if there is any other interpretation of $S_{n,k}$ in terms of pattern-avoiding permutations. The following conjecture will answer this question completely, if true.

\begin{conjecture}\label{schroder:asc}
Let $(\sigma,\pi)$ be a pair of patterns of length $4$. Then,
$$
S_{n,k}=|\{\pi\in\S_n(\sigma,\pi): \last(\pi)-1=k\}|
$$
 for any $0\leq k<n$ if and only if $(\sigma,\pi)$ is one of the following nine pairs:
 \begin{align*}
 &(4321,3421),(3241,2341),(2431,2341),(4231,3241),\\
 &(4231,2431),(4231,3421),(2431,3241),(3421,2431),(3421,3241).
 \end{align*}
\end{conjecture}

\subsection{Double Eulerian equidistributions}
\subsubsection{Statistics}
Let $\pi\in\S_n$ be a permutation. The {\em {\bf v}alues of {\bf i}nverse {\bf d}escents} of $\pi$ is  
$$\VID(\pi):=\{2\leq i\leq n:\pi_i+1 \,\,\text{appears to the left of}\,\, \pi_i\},$$
which  is an important set-valued extension of ``$\ides$''. The {\em positions of {\bf l}eft-to-right {\bf ma}xima} of $\pi$ is $\LMA(\pi):=\{i\in[n]:\pi_i>\pi_j\,\, \text{for all $1\leq j<i$}\}$. Similarly, we can define the {\em positions of {\bf l}eft-to-right {\bf mi}xima} $\LMI(\pi)$, the {\em positions of {\bf r}ight-to-left {\bf ma}xima} $\RMA(\pi)$ and  the {\em positions of {\bf r}ight-to-left {\bf mi}nima} $\RMI(\pi)$ of $\pi$.

Let $e\in\I_n$ be an inversion sequence. The positions of the {\em last occurrence of {\bf dist}inct positive entries} of $e$ is $\DIST(e):=\{2\leq i\leq n: e_i\neq0\,\,\text{and $e_i\neq e_j$ for all $j>i$}\}$. The {\em  positions of {\bf zero}s in $e$} is $\ZERO(e):=\{i\in[n]: e_i=0\}$. The {\em positions of the {\bf e}ntries of $e$ that achieve {\bf ma}ximum} is $\EMA(e):=\{i\in[n]: e_i=i-1\}$ and the {\em positions of {\bf r}ight-to-left {\bf mi}nima} of~$e$ is $\RMI(e):=\{i\in[n]: e_i<e_j\,\, \text{for all $ j>i$}\}$.

\subsubsection{A sextuple equidistribution}
\label{sec:sex}
\begin{figure}
\hspace{1.4cm}
\scalebox{0.8}{
\begin{tikzpicture}[scale=.5,]
\draw[step=1,color=gray] (7,1) grid (14,8); 
\draw [very thick,color=red](7,1)--(8,1);
\draw [very thick](8,2)--(9,2);
\draw [very thick,color=red](9,1)--(10,1);
\draw [very thick](10,2)--(11,2);
\draw [very thick](11,3)--(12,3);
\draw [very thick,color=red](12,1)--(13,1);
\draw [very thick](13,5)--(14,5);

\draw [color=blue](-0.1,0)--(-0.1,0);
\draw [color=blue](7,1)--(14,8);
\draw(7.5,0.5) node{$0$};
\draw(8.5,0.5) node{$1$};
\draw(9.5,0.5) node{$0$};
\draw(10.5,0.5) node{$1$};
\draw(11.5,0.5) node{$2$};
\draw(12.5,0.5) node{$0$};
\draw(13.5,0.5) node{$4$};
\draw(16,5) node{$\mapsto$};
\draw(15.95,5.6) node{$d$};

\draw[step=1,color=gray] (18,1) grid (25,8); 
\draw [color=blue](18,1)--(25,8);
\draw [very thick,color=red](18,1)--(19,1);
\draw [very thick](19,1)--(19,2)--(20,2);
\draw [very thick,color=red](20,2)--(21,2);
\draw [very thick](21,2)--(22,2)--(22,3)--(23,3);
\draw [very thick,color=red](23,3)--(24,3);
\draw [very thick](24,3)--(24,5)--(25,5)--(25,8);
\end{tikzpicture}
}
\caption{The outline of inversion sequence $(0,1,0,1,2,0,4)$.\label{fig:outline}}
\end{figure}

Note that an inversion sequence avoids $021$ if and only if its positive entries are weakly increasing, which inspires the following geometric representation. 

\begin{Def}[Outline]\label{outline}
Recall that a {\em Dyck path} of length $n$ is a lattice path in $\N^2$ from $(0,0)$ to $(n,n)$ using the
{\em east step} $(1,0)$ and the {\em north step} $(1,0)$, which does not pass above the line $y=x$.
Here a Dyck path will be represented as $d_1d_2\ldots d_n$, where $d_i$ is the height of its $i$-th east step.
For each $e\in\I_n(021)$, we associate it with a two-colored Dyck path $d(e)=d_1d_2\ldots d_n$, where the red
east steps indicate the positions of zero entries of $e$ like this: 
$$
d_{i}=
\begin{cases}
\,\,e_i\quad&\text{if $e_i\neq0$},\\
\,\,k\quad&\text{if $e_i=0$ and $k=\max\{e_1,\ldots,e_i\}$}.
\end{cases}
$$
For example, if $e=(0,1,0,1,2,0,4)\in\I_7(021)$, then $d(e)$ is the two-colored Dyck path in \cref{fig:outline}. The two-colored Dyck path $d(e)$ is called the {\em outline} of $e$. 
We introduce the {\em {\bf \em expo}sed positions} of $e$ as 
$$
\EXPO(e):=\{i: i\notin\mathcal{C}(e) \text{ and $i-d_i<j-d_j$ for all $j>i$ }\},
$$
where $\mathcal{C}(e)=\{i:\text{$e_i=0 $ and there is $(a,b)$, $a<i<b$, satisfying $e_a=e_b\neq0$}\}$.
Continuing with our example, we have $\EXPO(e)=\{2,7\}$.
\end{Def}


\begin{theorem}\label{thm:sex} 
There exists a bijection $\Psi:\I_n(021) \rightarrow \S_n(2413,4213)$ such that
$$
(\DIST,\ASC,\ZERO,\EMA,\RMI,\EXPO)e=(\VID,\DES,\LMA,\LMI,\RMA,\RMI)\Psi(e)
$$
for each $e\in\I_n(021)$.
\end{theorem}

The idea of constructing $\Psi$ is to draw lines parallel to the diagonal $y=x$ in some specified order and successively label the east steps (of the outline) touched by them. The details are provided in~\cite{kl}. \cref{thm:sex} has two interesting applications: (i) the calculation of the double Eulerian distribution $(\des,\ides)$ on $\S_n(2413,4213)$ using the natural structure of two-colored Dyck paths; (ii) an interpretation of the $\gamma$-coefficients of $S_n(t)$ in terms of $021$-avoiding inversion sequences via the so-called {\em Foata--Strehl group action}, which implies the palindromicity and {\em unimodality} of $S_n(t)$.

\subsubsection{Two more equidistributions}
Based on calculations, Martinez and Savage~\cite{ms} suspected that 
$$
\sum_{e\in\I_n(021)}t^{\asc(e)}=\sum_{e\in\I_n(\geq,\neq,\geq)}t^{\asc(e)}=\sum_{e\in\I_n(>,-,\geq)}s^{\asc(e)}.
$$
This follows from \cref{thm:sex}, the palindromicity of $S_n(t)$ and two more multivariate equidistributions (\cref{equi:1,equi:2}) stated below. 

First we introduce a set-valued extension of ``$\dist$'' different from ``$\DIST$'': 
$$
\ROW(e):=\{e_1,e_2,\ldots,e_n\}\setminus\{0\},\ \text{for each $e\in\I_n$}.
$$
\begin{theorem}\label{equi:1}For $n\geq1$, we have 
$$
\sum_{e\in\I_n(\geq,\neq,\geq)}s^{\ROW(e)}t^{\ASC(e)}u^{\last(e)}=\sum_{e\in\I_n(>,-,\geq)}s^{\ROW(e)}t^{\ASC(e)}u^{\last(e)}.
$$
\end{theorem}
\begin{proof}
We can  construct a bijection from $\I_n(\geq,\neq,\geq)$ to $\I_n(>,-,\geq)$, which preserves the triple statistics $(\ROW,\ASC,\last)$. Notice that $\I_n(\geq,\neq,\geq)=\I_n(\blue{110},101,201,210)$, while
$\I_n(>,-,\geq)=\I_n(\blue{100},101,201,210)$. The idea is to replace iteratively occurrences
of pattern $100$ in an inversion sequence in $\I_n(\geq,\neq,\geq)\setminus\I_n(>,-,\geq)$ with those of patterns $110$, the details of which will be omitted here.
\end{proof}

Recently, Baril and Vajnovszki~\cite{bv} constructed a new coding $\Phi:\S_n\rightarrow\I_n$ satisfying 
$$
(\VID,\DES,\LMA,\LMI,\RMA)\pi=(\DIST,\ASC,\ZERO,\EMA,\RMI)\Phi(\pi)
$$
for each $\pi\in\S_n$.
\begin{theorem}\label{equi:2}For $n\geq1$, we have 
$$
\sum_{\pi\in\S_n(3142,3124)}s^{\VID(\pi)}t^{\DES(\pi)}=\sum_{e\in\I_n(\geq,\neq,\geq)}s^{\DIST(e)}t^{\ASC(e)}.
$$
\end{theorem}
\begin{proof}
We can show that the Baril--Vajnovszki coding $\Phi$ restricts to a bijection between $\S_n(3124,3142)$ and $\I_n(\geq,\neq,\geq)$. The details are omitted here. 
\end{proof}

\begin{remark}
Interestingly, we have also been able to show that $\Phi$ restricts to a bijection between $\S_n(2413,4213)$ and $\I_n(021)$. This restricted $\Phi$ does not transform ``$\RMI$'' to ``$\EXPO$'', while  our bijection $\Psi$ in \cref{thm:sex} does. 
\end{remark}
\vspace{-3ex}

\section{Baxter numbers}
\label{sec:bax}
 A permutation avoiding both {\em vincular patterns} (see~\cite{ki} for the definition) $2\underline{41}3$ and $3\underline{14}2$ is called a {\em Baxter permutation}. It is a result of Chung et al.~\cite{chung} that
$$
B_n=|\S_n(2\underline{41}3,3\underline{14}2)|=\frac{1}{{n+1\choose1}{n+1\choose2}}\sum_{k=0}^{n-1}{n+1\choose k}{n+1\choose k+1}{n+1\choose k+2}.
$$
The number $B_n$ is known as the $n$-th {\em Baxter number}. Martinez and Savage~\cite{ms} conjectured that $|\I_n(\geq,\geq,>)|=B_n$, which can be refined as follows.


\begin{theorem}\label{thm:baxter}
For $n\geq1$, we have the equidistribution
\begin{equation}\label{bax:equi}
\sum_{e\in\I_n(\geq,\geq,>)}u^{n+1-\cri(e)}=\sum_{\pi\in\S_n(2\underline{41}3,3\underline{14}2)}u^{\lma(\pi)+\rma(\pi)}.
\end{equation}
\end{theorem}

\begin{corollary}
Define the Baxter triangle as $B_{n,k}:=|\{e\in\I_n(\geq,\geq,>): \last(e)=k\}|$. Then, 
$$
B_{n,k}=|\{\pi\in\S_{n-1}(2\underline{41}3,3\underline{14}2): \lma(\pi)+\rma(\pi)\geq n-k\}|.
$$
\end{corollary}

The rest of this section is devoted to a  sketch of our proof of \cref{thm:baxter}.
For each $e\in\I_n(\geq,\geq,>)$, introduce the {\em parameters} $(p,q)$ of $e$, where $p=m+1-\cri(e)$ and $q=n-m$ with $m=\max\{e_1,\ldots,e_n\}$. 
After a careful discussion we can obtain the following new rewriting rule (see~\cite{bcfmm} for other known rewriting rules for Baxter families).

\begin{lemma}\label{lem:baxeter}
Let $e\in\I_n(\geq,\geq,>)$ be an inversion sequence with parameters $(p,q)$. Exactly $p+q$ inversion sequences in $\I_{n+1}(\geq,\geq,>)$ when removing their last entries will become $e$, and their  parameters are respectively:
\begin{align*}
&(p-1,q+1), (p-2,q+1), \ldots, (1,q+1), \\
&(1,q+1), (p+1,q), (p+2,q-1),\ldots, (p+q,1).
\end{align*}
The order in which the parameters are listed corresponds to the inversion sequences with last entries from $c$ to $n$, where $c=n+1-(p+q)$.
\end{lemma}

Define the formal power series $F(t;u,v)=F(u,v):=\sum_{n,p,q\geq1}F_{n,p,q}t^nu^pv^q$, where $F_{n,p,q}$ is the number of inversion sequences in $\I_n(\geq,\geq,>)$ with parameters $(p,q)$. We can turn the above lemma into a functional equation as follows. 
\begin{proposition}We have the following equation for $F(u,v)$:
\begin{equation}\label{eq:baxter}
\biggl(1+\frac{tv}{1-u}+\frac{tv}{1-v/u}\biggr)F(u,v)=tuv+tuv\biggl(1+\frac{1}{1-u}\biggr)F(1,v)+\frac{tv}{1-v/u}F(u,u).
\end{equation}
\end{proposition}

Let 
$G(u,v):=\sum_{n\geq1}t^n\sum_{\pi\in\S_n(2\underline{41}3,3\underline{14}2)}u^{\lma(\pi)}v^{\rma(\pi)}$.
This formal power series $G(u,v)$ was first introduced and studied by Bousquet-M\'elou~\cite{bo}.  
Now, \cref{thm:baxter} is equivalent to $G(u,u)=F(u,u)$, which will be established by solving~\eqref{eq:baxter}.

\begin{proof}[Proof of \cref{thm:baxter}]
It will be convenient to set $w=v/u$ in~\eqref{eq:baxter}. The equation then becomes
$$
\biggl(1+\frac{tuw}{1-u}+\frac{tuw}{1-w}\biggr)F(u,wu)=tu^2w+tu^2w\biggl(1+\frac{1}{1-u}\biggr)F(1,wu)+\frac{tuw}{1-w}F(u,u).
$$
Further setting $u=1+x$ and $w=1+y$ in the above equation yields
\begin{multline}\label{eq:bax}
\frac{xy-t(1+x)(1+y)(x+y)}{t(1+x)(1+y)}F(1+x,(1+x)(1+y))\\
=xy(1+x)-(1-x^2)yF(1,(1+x)(1+y))-\widetilde{F}(x),
\end{multline}
where $\widetilde{F}(x):=xF(1+x,1+x)$. We call the numerator $K(x,y)$ of the coefficient of
$F(1+x,(1+x)(1+y))$ the {\em kernel} of the above equation:
$$
K(x,y)=xy-t(1+x)(1+y)(x+y).
$$
We are going to apply the so-called {\em kernel method} (cf.~\cite{bo}) to this equation. 

As a polynomial in $y$, the kernel has two roots:
$$
Y(x)=\frac{1-t(1+x)(1+\bar{x})-\sqrt{1-2t(1+x)(1+\bar{x})-t^2(1-x^2)(1-\bar{x}^2)}}{2t(1+\bar{x})},
$$
$$
Y'(x)=\frac{1-t(1+x)(1+\bar{x})+\sqrt{1-2t(1+x)(1+\bar{x})-t^2(1-x^2)(1-\bar{x}^2)}}{2t(1+\bar{x})},
$$
where $\bar{x}=1/x$. Only the first root can be substituted for $y$ in~\eqref{eq:bax}, because the term
$F(1+x,(1+x)(1+Y'))$ is not a well-defined power series in $t$ (the Taylor expansion of $Y'$ in $t$
does not exist). 

Now, we will adopt the {\em obstinate kernel method} that was invented by Bousquet-M\'elou~\cite[Section~2.2]{bo} for producing all the pairs $(x,y)$ that can be legally substituted in~\eqref{eq:bax}: those are the pairs $(x,Y), (\bar{x}Y,Y), (\bar{x}Y,\bar{x})$ and their dual $(Y,x), (Y,\bar{x}Y), (\bar{x},\bar{x}Y)$, thanks to the symmetry of the kernel $K(x,y)$. Substituting these 6 pairs into~\eqref{eq:bax} and after some manipulations, we obtain
{\small
\begin{equation*}
\begin{cases}
\,\,(x-xY^2)\widetilde{F}(x)-(Y-x^2Y)\widetilde{F}(Y)=(Y-Y^3)(x^2+x^3)-(x-x^3)(Y^2+Y^3),
\\
\,\,(Y\bar{x}-Y^3\bar{x})\widetilde{F}(Y\bar{x})-(Y-Y^3\bar{x}^2)\widetilde{F}(Y)=(Y-Y^3)(Y^2\bar{x}^2+Y^3\bar{x}^3)-(Y\bar{x}-Y^3\bar{x}^3)(Y^2+Y^3),
\\
\,\,(Y\bar{x}-Y\bar{x}^3)\widetilde{F}(Y\bar{x})-(\bar{x}-Y^2\bar{x}^3)\widetilde{F}(\bar{x})=(\bar{x}-\bar{x}^3)(Y^2\bar{x}^2+Y^3\bar{x}^3)-(Y\bar{x}-Y^3\bar{x}^3)(\bar{x}^2+\bar{x}^3).
\end{cases}
\end{equation*}
}
By eliminating $\widetilde{F}(Y)$ and $\widetilde{F}(Y\bar{x})$, we get a relation between $\widetilde{F}(x)$ and $\widetilde{F}(\bar{x})$:
\begin{equation}\label{main:baxe}
\widetilde{F}(x)+\widetilde{F}(\bar{x})=\frac{Y(1+x)(x^4-2Yx^3+2Y^2x-2Y+1)}{x^2(Y-1)(Y-x)}.
\end{equation}
But $\widetilde{F}(x)=xF(1+x,1+x)$ is a formal power series in $t$ with coefficients in $x\N[x]$, while $\widetilde{F}(\bar{x})$ is a formal power series in $t$ with coefficients in $\bar{x}\N[\bar{x}]$. Therefore, the positive part in $x$ of the right hand side of~\eqref{main:baxe} is exactly $\widetilde{F}(x)$.

On the other hand, it has been showed in~\cite[Corollary~3]{bo} that if we let
$\widetilde{G}(x):=xG(1+x,1+x)$, then
\begin{equation}
\frac{x-2t(1+x)^2}{t(1+x)^2}\widetilde{G}(x)=x^2-2R(x),
\end{equation}
where $R(x)=xG(1+x,1)$.
Combining with the relation between $R(x)$ and $R(\bar{x})$ proved in~\cite[Eq.~(8)]{bo}:
$$
R(x)+R(\bar{x})=\bar{x}^2Y(1+x^3-xY),
$$
we have 
\begin{align*}\label{eq:bousquet}
\widetilde{G}(x)+\widetilde{G}(\bar{x})&=\frac{t(1+x)^2}{x-2t(1+x)^2}(x^2+\bar{x}^2-2(R(x)+R(\bar{x})))\\
&=\frac{t(1+x)^2}{x-2t(1+x)^2}(x^2+\bar{x}^2-2\bar{x}^2Y(1+x^3-xY)).
\end{align*}
To check that $\frac{t(1+x)^2}{x-2t(1+x)^2}(x^2+\bar{x}^2-2\bar{x}^2Y(1+x^3-xY))$ equals the right hand side
of~\eqref{main:baxe} is routine by Maple, which proves that $\widetilde{F}(x)=\widetilde{G}(x)$.
This completes the proof. 
\end{proof}

Since the proof of equidistribution~\eqref{bax:equi} uses the obstinate kernel method based on the formal
power series, it is natural to ask for  a bijective proof.
\vspace{-2ex}

%%%%%%%%%%%%%%%%%%%%%%%
\section{Euler numbers}
%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Entringer--Eulerian statistics on $\I_n(000)$}
As introduced by Simion and Sundaram~\cite{sun}, a permutation $\pi\in\S_n$ is called a
{\em Simsun permutation} if it has no double descents, even after removing $n,n-1,\ldots,k$ for any $k$.
Let $RS_n$ be the set of all Simsun permutations in $\S_n$. Using the statistic ``$\last$'',
we refine a result \cite[Corollary~2]{cor} by Corteel et al.
\begin{theorem}Let $\asc(\pi):=n-1-\des(\pi)$ for each $\pi\in\S_n$. Then, 
$$
\sum_{\pi\in RS_n} t^{\asc(\pi)}u^{\last(\pi)}=\sum_{e\in\I_n(000)}t^{\dist(e)}u^{\last(e)+1}.
$$
\end{theorem}
\begin{proof}
By combining the simple bijection in~\cite[Theorem~7]{cor} from $\I_n(000)$ to {\em$0$-$1$-$2$-increasing trees} with $n+1$ vertices and a special ordering of the {\em increasing tree representation} of permutations due to Maria Monks (see~\cite[Page~198]{st}).
\end{proof}

It also follows from the simple bijection in~\cite[Theorem~7]{cor} and a result of
Poupard~\cite[Proposition~1]{pou} that the statistic ``$\last+1$'' is {\em Entrianger}.
Can the generating function for this Entrianger--Eulerian pair be calculated? 
 
\subsection{Double Eulerian distribution on $\I_n(000)$}
As an application of Foata's  V-code and  S-code, we can prove  the following double Eulerian equidistribution.
\begin{theorem}\label{dou:sim}
Let $\iasc(\pi):=\asc(\pi^{-1})$ for each $\pi\in\S_n$. Then,
$$
\sum_{\pi\in RS_n} s^{\iasc(\pi)}t^{\asc(\pi)}=\sum_{e\in\I_n(000)}s^{\asc(e)}t^{\dist(e)}.
$$
\end{theorem}
 
The details for the proof of a set-valued extension of \cref{dou:sim} will be reported in a full version of this abstract.

\printbibliography


\end{document}
